1. Field of the Invention
The present invention relates to communications devices, specifically devices that enable packet forwarding and handling in communications networks.
2. Description of the Related Art
In a communications network, routing devices receive messages at one of a set of input interfaces and forward them on to one of a set of output interfaces. Users typically require that such routing devices operate as quickly as possible in order to keep up with the high rate of incoming messages. In a packet routing network, where information is transmitted in discrete chunks or xe2x80x9cpacketsxe2x80x9d of data, each packet includes a header. The header contains information used for routing the packet to an output interface and subsequent forwarding to a destination device. The packet may also be forwarded to another router for further processing and/or forwarding. Header information used for routing may include the destination address and source address for the packet. Additionally, header information such as the destination device port, source device port, protocol, packet length, and packet priority may be used. Header information used by routing devices for administrative tasks may include information about access control, accounting, quality of service (QoS), or class of service (CoS).
FIG. 1 is a generic packet routing/switching system 100 that will be used to describe both the prior art and the invention. A well-known routing device or switch 100 consists of a set of linecards 110 and a switching fabric 120. Each linecard 110 includes an input interface 111, an output interface 112, a fabric interface 170, and a control element 130. Linecards 110 connect to communications network 1, which may be any form of local, enterprise, metropolitan, or wide area network known in the art, through both input interface 111 and output interface 112. More than one input interface 111 may be provided, with each interface carrying a fraction of the full capacity of control element 130.
Control element 130 is configured to receive inbound packets 113 (i.e., packets entering the system from network 1) from input interface 111, process the packet, and transmit it through fabric interface 170 to switching fabric 120 through which it is sent to another (or the same) linecard 110 for further processing. This path is referred to as the xe2x80x9creceivexe2x80x9d path into the device from the network.
Outbound packets 114 (i.e., those to be transmitted out of the switch device) are received from switching fabric 120 through fabric interface 170, processed in control element 130, and transmitted to network 1 on output interface 112. Accordingly, this path is known as the xe2x80x9ctransmitxe2x80x9d path from the device to the network.
As known in the prior art, control element 130 consists of an inbound packet receiver 140, lookup circuit 145, inbound memory controller 150, first memory 160, outbound memory controller 150, second memory 160, and outbound transmitter 180. Control circuits 190 are also provided to perform configuration, initialization, statistics collection, and accounting functions as well as to process certain exception packets.
In a manner well-known in the art, packets are received from the physical medium of the network at input interface 111. The inbound packet receiver 140 operates in conjunction with lookup circuit 145 to determine routing treatments for inbound packets 113. Lookup circuit 145 includes routing treatment information disposed in a memory data structure. Access and use of this information in response to data in the header of inbound packet 113 is accomplished with means well-known in the router art. These routing treatments can include one or more of the following:
selection of one or more output interfaces to which to forward inbound packets 113 responsive to the destination device, to the source and destination device, or to information in any other packet header fields (packets may also be dropped, i.e., not forwarded);
determination of access control list (ACL) treatment for inbound packets 113:
determination of class of service (CoS) treatment for inbound packets 113;
determination of one or more accounting records or treatments for inbound packets 113; and
determination of other administrative treatment for inbound packets 113.
Examples of such systems may be found in U.S. Pat. No. 5,088,032, METHOD AND APPARATUS FOR ROUTING COMMUNICATIONS AMONG COMPUTER NETWORKS to Leonard Bosack; U.S. Pat. No. 5,509,006, APPARATUS AND METHOD FOR SWITCHING PACKETS USING TREE MEMORY to Bruce Wilford et al.; U.S. Pat. No. 5,852,655, COMMUNICATION SERVER APPARATUS HAVING DISTRIBUTED SWITCHING AND METHOD to John McHale et al.; and U.S. Pat. No. 5,872,783, ARRANGEMENT FOR RENDERING FORWARDING DECISIONS FOR PACKETS TRANSFERRED AMONG NETWORK SWITCHES to Hon Wah Chin, incorporated in their entireties herein by reference.
One shortcoming known in the prior art arises from the ever-increasing need for speed in network communications. Attempts to scale prior art routers and switches to gigabit speed have shown that architectures that require a deep packet buffering prior to determining routing treatment suffer from high packet latency. Many distributed routing schemes, such as that described above wherein routing is performed in each linecard on packet receipt, have had only limited success in providing the necessary increase in throughput speed.
A related limitation has been the inability of a general purpose digital computer to perform the necessary lookup and queue management functions using software in real time, i.e., approaching the wire speed (line rate) of the incoming packets. As the need for increased packet throughput has grown, software-based systems have been shown to lack sufficient scaleability to the demands of modern internetworking systems.
A further drawback is the lack of flexibility in prior art systems tuned for speed with hardware implementations of functions once performed by software. As the hardware is less able to be reconfigured without redesign, these prior art designs are often rendered obsolete by the adoption of new standards and communications protocols.
A still further drawback of prior art systems is their relative inability to rapidly provide a range of services based on packet priority, as represented by various fields in the packet header. Such systems are often described as providing type of service (TOS), quality of service (QoS), or class of service (CoS) routing. Prior art systems typically experience additional packet latency and throughput reduction when performing routing based on packet priority.
What is needed is a flexible switch system, preferably distributed on a linecard, that provides ultra-high throughput packet switching based at least in part on packet priority. The system architecture should be able to be reconfigured to handle a variety of network protocols and optimizations. In particular, low latency switching determined by individual packet class of service is desired. Such a linecard should operate as close to line rate as possible, i.e., at or near the maximum speed of transmission over the physical medium and without any appreciable buffering delay.
A high speed hardware-based dequeuing apparatus and method for switching packets in a communications network is disclosed. The dequeuing apparatus is part of a linecard consisting of two transmission paths: the receive path, which carries packets into the switch device from the network and the transmit path, which carries packets from the switch to the network. While each linecard typically has both a receive and a transmit path, such an arrangement is not essential. Separate transmit and receive linecards employing the architecture of the present invention are also possible.
In the receive path, packets are processed and switched in an asynchronous, multi-stage pipeline that operates on several packets at the same time to determine each packet""s routing destination. Once that determination is made, each packet is modified to contain new routing information as well as additional header data to help speed it through the switch. Each packet is then buffered and enqueued for transmission over the switching fabric to the linecard attached to the proper destination port. The destination linecard may be the same physical linecard as that receiving the inbound packet or a different physical linecard. The hardware dequeuing apparatus is employed to rapidly remove packets from the buffer in the process of sending packets over the fabric while providing class of service- (CoS-) based service differentiation.
The transmit path consists of a buffer/queuing circuit similar to that used in the receive path, with the same hardware-based dequeuing apparatus.
The dequeuing apparatus used in both the receive and transmit paths on the linecard implements a variation of the well-known Deficit Round Robin (DRR) software-based dequeuing algorithm in dedicated, special-purpose circuits. In an alternate embodiment of the present invention, an enhanced algorithm called Modified DRR (MDRR) is provided by the hardware apparatus of the present invention. The MDRR apparatus enhances DRR performance by creating a special, high priority queue that services packets showing a higher class of service (CoS) indication. In addition, by implementing the algorithm in dedicated hardware (rather than software), the present invention greatly enhances speed of execution and enables high switch throughput rates.